本篇內容

• 介紹 Yacc語法中的優先級: nonassoc & prec
• 範例 - 簡易計算機5

前言

我們昨天介紹了Yacc語法中的優先級left & right，可以將特定的token設定為較高的優先級，在規則匹配時就可以避免衝突發生。然而，如果是同一個token，在不同的規則(字串組合)時，能否設定不同的優先級呢？

優先級(2) 減法或負號?

我們來看看負數的四則運算。在這裡，我們碰到了以下兩大困難：

1. 負號與減法符號都是”-”，編譯器要怎麼辨識出這兩個類別?
2. 負號與減法符號的優先級並不相同(負號優先級最高，減法符號優先級較低)，該如何定義之?

第二個問題可以使用nonassoc這個語法來解決。nonassoc表示最高的優先級，優先於剛剛介紹的left跟right，且與其左右的token沒有任何關聯。因此，我們可以將”負號”這個規則取一個名字(在下面的例子中，我們將其定義為UMINUS)，並用nonassoc定義其優先級。

%nonassoc UMINUS

接著，我們要回頭解決第一個問題了。即使負號與減法符號都是”-”，其使用情境卻不一樣。減法符號兩邊皆需要有運算單元(像是數字)，負號則只有右邊有數字。因此，我們可以在Yacc的規則中，把兩者區別出來，並利用prec這個語法來賦予負號最高的優先級。下面是完整的四則運算規則的語法。

expr:
      NUM_T                 { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }
    | '-' expr %prec UMINUS { $$ = -$2; }
    ;

範例 - 簡易計算機5

說明

請實作出一個簡易的計算機，能夠對多個整數(無論正負)做四則運算(加減乘除)，符合運算優先順序為小括號→乘除法→加減法，並回傳結果。

程式實作

Lex

• 基本上，lex檔案內容與昨天相同

%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)
expressions ([-+*/()])

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
{expressions}   { return yytext[0]; }
{blank_chars}   { ; }
"="             { return yytext[0]; }
\n              { ; }

%%

int yywrap(void) {
    return 1;
}

Yacc

• 在Definition區塊新增負號的優先級
• 新增負數的Rules

%{
#include "main.h"

void yyerror(const char *s);
extern int yylex();
extern int yyparse();

%}

%token NUMBER
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%%

func:
      expr '='              { printf("Result: %d\n", $1); }
    ;

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }
    | '-' expr %prec UMINUS { $$ = -$2; }
    | '(' expr ')'          { $$ = $2; }
    ;

%%

void yyerror(const char *s) {
    cerr << s << endl;
}

執行結果

輸入內容

4 * (-7) + 28 / 4 =

輸出結果

Result: -21

結語

至此，我們成功完成整數的四則運算了！

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
• Tom Niemann. Lex & Yacc